package Kadane算法;

/**
 * 918. 环形子数组的最大和
 * 给定一个长度为 n 的环形整数数组 nums ，返回 nums 的非空 子数组 的最大可能和 。
 *
 * 解题思路:
 *  环形数组的最大和问题可以通过两个步骤解决：
 *      1：常规子数组的最大和：计算数组中连续子数组的最大和，不考虑环形结构；
 *      2：环形结构下的最大和：当最大子数组跨越数组的两端时，可以通过计算数组的总和再减去非环形的最小子数组和得到。
 *  具体步骤如下：
 * 使用 Kadane 算法计算常规的最大子数组和。
 * 使用类似 Kadane 算法的方法计算常规的最小子数组和。
 * 计算数组的总和。
 * 如果总和等于最小子数组和（即所有元素都是负数），则直接返回常规的最大子数组和。
 * 否则，比较常规的最大子数组和与（总和 - 最小的连续子数组和），取最大值作为结果。
 */
public class L_918 {

    public int maxSubarraySumCircular(int[] nums) {
        // 计算常规的最大子数组和
        int maxSub = maxSubarray(nums);
        // 计算常规的最小子数组和
        int minSub = minSubarray(nums);

        // 计算数组的总和
        int total = 0;
        for (int num : nums) {
            total += num;
        }

        // 如果所有元素都是负数，总和等于最小子数组和
        if (total == minSub) {
            return maxSub;
        }

        // 取常规最大值或总和减去最小子数组和的较大者
        return Math.max(maxSub, total - minSub);
    }


    // 计算常规最小子数组的和
    private int minSubarray(int[] nums){
        int currentMin = nums[0];
        int minSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentMin = Math.min(nums[i],currentMin + nums[i]);
            minSum = Math.min(minSum,currentMin);
        }
        return minSum;
    }

    // 计算常规最大子数组的和
    private int maxSubarray(int[] nums){
        int currentMax = nums[0];
        int maxSum = nums[0];
        for (int i = 1; i < nums.length; i++) {
            currentMax = Math.max(nums[i],currentMax + nums[i]);
            maxSum = Math.max(maxSum,currentMax);
        }
        return maxSum;
    }
}
